package com.scheuk.puzzles;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Hashtable;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.StringTokenizer;

public class BrickPuzzle {

	static int[] blocks = {6,9};
	
	static Map<Integer, String> map = new HashMap<Integer, String>();
	static Hashtable<Integer, List> lookup = new Hashtable<Integer, List>();
	static Hashtable<Integer, Long> tally = new Hashtable<Integer, Long>();
	
	private final static String SEPARATOR = ".";
	
	public static long SolveBrickPuzzle(double wallLength, int wallHeight)
	{
		Arrays.sort(blocks);
		int wall = (int) Math.round(wallLength * 2);
		findRowTypes(wall, blocks, map, new StringBuffer(), 0);
		List<Integer> rows = FindMatchingRows(map, lookup);

		//Hashtable for storing bucket list of valid rows
		for (Iterator iter = rows.iterator(); iter.hasNext(); )
		{
			tally.put((Integer) iter.next(), (long) 1);
		}
		return CountRows(lookup, tally, wallHeight);
	}
	
	/* Find all the ways to create a single row of the given width. 
	 * Reduce the remaining length of width with a block
	 * until a valid row is found. If first block doesn't fit, try next
	 * block. Once a valid row is found, save into map.
	 */
	public static void findRowTypes(int remainingLength, int[] blocks, Map<Integer, String> map, StringBuffer row, int prevBlock)
	{
		for(int i = 0; i < blocks.length; i++)
		{
			StringBuffer newrow = new StringBuffer(row);
			int newLength = remainingLength;
			int nextBlock = prevBlock;
			if (newLength - blocks[i] >= 0)
			{
				newLength-=blocks[i];
				nextBlock+=blocks[i];
				newrow.append(SEPARATOR + Integer.toString(nextBlock));
			} else {
				break;
			}
			if (newLength == 0) {
				//chop off the last block of a valid row type to make it easier for comparison later on
				int removal = Integer.toString(nextBlock).length()+1;
				newrow.delete(newrow.length() - removal, newrow.length());
				map.put(map.size(), newrow.toString().trim());
			} else {
				findRowTypes(newLength, blocks, map, newrow, nextBlock);
			}
		}
	}
	
	/* For each row type in the map, find other matching row types and store their
	 * indexes into a lookup table.
	 * 
	 * This is the slowest section of code due to the three for loops. However,
	 * the subset of elements being looped through are relatively small.  
	 */
	public static List<Integer> FindMatchingRows(Map map, Hashtable lookup)
	{
		List<Integer> startingList = new ArrayList<Integer>();
		
		for (int i = 0; i < map.size(); i++)
		{
			String row = (String) map.get(i);
			List<Integer> matches = new ArrayList<Integer>();
			for (int j = 0; j < map.size(); j++)
			{
				StringTokenizer tokens = new StringTokenizer(row, SEPARATOR);
				String checkRow = (String) map.get(j) + SEPARATOR;
				boolean valid = true; 
				while(tokens.hasMoreTokens())
				{	
					String token = tokens.nextToken();
					token = SEPARATOR + token + SEPARATOR;
					if (checkRow.indexOf(token) > -1)
					{
						valid = false;
						break;
					} else {
						continue;
					}
				}
				if(valid == true) {
					matches.add(j);
				}
			}
			lookup.put(i, matches);
			startingList.add(i);
		}
		return startingList;
	}
		
	/* Find all the ways to build stacks of the given height using the lookup table of
	 * valid rows and associated neighboring rows and a table storing list of possible
	 * ways to create the previous row. 
	 */
	public static long CountRows(Hashtable<Integer, List> lookup, Hashtable<Integer, Long> panel, int wallHeight)
	{
		if (wallHeight > 1) 
		{
			Hashtable<Integer, Long> nextPanel = new Hashtable<Integer, Long>();
			for (Entry<Integer, Long> entry : panel.entrySet())
			{	
				Integer keyrow = entry.getKey();
				Long rowCount = entry.getValue();
				if (rowCount > 0)
				{
					List neighbors = lookup.get(keyrow);
					for(int i = 0; i < neighbors.size(); i++)
					{
						int neighborRow = (Integer) neighbors.get(i);
						Long currentCount = (nextPanel.get(neighborRow) == null) ? 0 : nextPanel.get(neighborRow);
						nextPanel.put(neighborRow, currentCount+rowCount);
					}
				}
			}
			return CountRows(lookup, nextPanel, wallHeight-1);
		}
		long count = 0;
		for (Entry<Integer, Long> entry : panel.entrySet())
		{
			Long rowTally = (Long) entry.getValue();
			count+=rowTally;
		}
		return count;
	}
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		long st = System.currentTimeMillis();
		//long answer = SolveBrickPuzzle(Double.parseDouble(args[0]), Integer.parseInt(args[1]));
		long answer = SolveBrickPuzzle(48, 10);
		long end = System.currentTimeMillis();
		System.out.println((end - st) + "ms");
		System.out.println(answer);

	}
}
